\chapter{Implementação do protocolo}
\label{cap:implementacao}

Neste capítulo falaremos de principais funcionalidades implementadas no protocolo e na última seção 
\ref{sec:simulador} falaremos um pouco do simulador de rede - NS.

O protocolo foi implementado em C++ e criamos cenários para simulação usando OTcl. Para tal, instalamos o NS;
criamos um diretório (manet-trp) onde colocamos todos os arquivos criados para o nosso protocolo.

Para explicar principais funcionalidades do processo de desenvolvimento, primeiro vamos explicar os arquivos
de código fonte (em C++) criados; depois, arquivos de código fonte (em C++ e OTcl) alterados.

\section{Descrição dos arquivos criados}
\subsection{wtrp.h}
\label{impl:wtrph}
Este arquivo contém definição de temporizadores e definição da classe principal
(WTRP) do protocolo (trecho de código \ref{header-wtrp}). A classe \textit{Generic\_timer} é uma classe genérica que
implementa os mecanismos necessários para que, ao expirar, um temporizador possa
executar alguma ação. A classe \textit{WTRP} herda da classe \textit{Agent}, e contém
todos os atributos e comportamentos necessários para representar um nódo (estação)
em uma rede \textit{ad-hoc} sem fio.

\begin{lstlisting}[label=header-wtrp, caption=Classes em wtrp.h]
/*Timers*/
class Generic_timer: public TimerHandler {

public:
	Generic_timer(WTRP *agent_, start_timer_function trigger_function_) :
			TimerHandler() {
			... ... ...
	}
protected:
	WTRP *generic_timerAgent_;
	start_timer_function trigger_fuction_;
	virtual void expire(Event *event);
};

class WTRP: public Agent {

protected:
	//Timers types
	Generic_timer solicitEntering_timer_;
			... ... ...

public:
	WTRP(nsaddr_t ID);

	void recv(Packet *packet, Handler *);
	int command(int, const char * const *);
};
\end{lstlisting}

\subsection{wtrp.cc}
\label{impl:wtrp}
wtrp.cc é o arquivo principal da nossa implementação. Ele
contém as funções que provêm mecanismos para ligação com OTcl, execução do protocolo inclusive
recepção e envio de dados.

\begin{lstlisting}[label=wtrp, caption=Classes em wtrp.cc]

int hdr_wtrp_packet::offset_;
static class WTRPHeaderClass: public PacketHeaderClass {
public:
	WTRPHeaderClass() :
			PacketHeaderClass("PacketHeader/WTRP", sizeof(hdr_all_packets)) {
		bind_offset(&hdr_wtrp_packet::offset_);
	}
} class_wtrp_hdr;

static class WTRPclass: public TclClass {
public:
	WTRPclass() :
			TclClass("Agent/WTRP") {
	}
	TclObject* create(int argc, const char* const * argv) {
		assert(argc == 5);
		return (new WTRP((nsaddr_t) Address::instance().str2addr(argv[4])));
	}
} class_wtrp;

WTRP::WTRP(nsaddr_t ID) :
		Agent(PT_WTRP), resetstate_timer_(this, &WTRP::clean_dataStructures), offlinestate_timer_(
				this, &WTRP::do_offline_timeout), solicitEntering_timer_(this,
				&WTRP::solicit_joinRing), collecting_repliers_timer_(this,
				&WTRP::contact_replier), solicit_setPredecessor_timer_(this,
				&WTRP::do_waitFor_predecessor_expired), release_token_timer_(
				this, &WTRP::transmitting_token), monitoringstate_timer_(this,
				&WTRP::transmitting_token), release_vtoken_timer_(this,
				&WTRP::transmitting_varal_token), vmonitoringstate_timer_(this,
				&WTRP::transmitting_varal_token), packetControlQueue() {

	/*Bind variables with OTcl*/
	/*Variables initialization, instance*/
	... ... ...
}

int WTRP::command(int argc, const char* const * argv) {

	if (argc == 2) {
		Tcl& tcl = Tcl::instance();

		if (strncasecmp(argv[1], "id", 2) == 0) {
			... ... ..
			
			return TCL_OK;
		}
		if (strncasecmp(argv[1], "start", 5) == 0) {
		        ... ... ...
			return TCL_OK;
		}

		if (strncasecmp(argv[1], "soliciting", 10) == 0) {
			... ... ...
			return TCL_OK;
		}

		if (strncasecmp(argv[1], "stopping", 8) == 0) {
			... ... ...
			return TCL_OK;
		}

	} else if (argc == 3) {

		if (strcmp(argv[1], "index") == 0) {
			... ... ...
			return TCL_OK;
		}


		else if (strcmp(argv[1], "drop-target") == 0) {
		      ... ... ...
		      
		      return TCL_OK
		}

		else if (strcmp(argv[1], "if-queue") == 0) {
			return TCL_OK;
		}

		else if (strcmp(argv[1], "port-dmux") == 0) {
			dmux_ = (PortClassifier *) TclObject::lookup(argv[2]);
			if (dmux_ == 0) {
				fprintf(stderr, "%s: %s lookup of %s failed\n", __FILE__,
						argv[1], argv[2]);
				return TCL_ERROR;
			}
			return TCL_OK;
		}
	}
	return Agent::command(argc, argv);
}

void WTRP::recv(Packet *p, Handler *handler) {

	... ... ...
	// if the packet is routing protocol control packet, give the packet to agent
	if (ch->ptype() == PT_WTRP) {
		ih->ttl_ -= 1;
		recv_protocol_packet(p);
		return;
	}

	... ... ...
	// This is data packet, find route and forward packet
	recv_data(p, handler, ch);
}

void WTRP::forward(Packet *p) {

}

/*Method for sending any kind of the token.*/
void WTRP::send_token_packet(nsaddr_t destination, u_int8_t frameControl,
		Packet *packet, int packet_size, double delay) {
	switch (frameControl) {

	case SET_PREDECESSOR:
	      break;
	}
	Scheduler::instance().schedule(target_, packet, delay);
}

//RECEIVING METHODS
/*It concerns about all protocol packet type*/
void WTRP::recv_protocol_packet(Packet* packet) {
	... ... ...

	switch (p_packet->getFC()) {

	case SOLICIT_ENTERING:
		break;
	case VARAL_SET_PREDECESSOR:
		break;
	case LEAVING_ALERT:
		break;
	default:
		break;
	}
}
\end{lstlisting}

No trecho de código \ref{wtrp}, as duas primeiras classes implementam a ligação entre interface Tcl com 
cabeçalho de pacote e agente WTRP, respectivamente. No construtor de agente WTRP destacamos o argumento  PT\_WTRP
da classe \textit{Agent}. Este argumento identifica qualquer pacote pertencente a um agente WTRP dentro do ambiente
NS2. O nosso agente herda o método \textit{command} da classe \textit{Agent}; \textit{argv[0]} armazena o nome do
método a ser invocado, \textit{argv[1]} armazena as instruções obrigatórias (por exemplo \textit{``start''}) e também
armazena as instruções que desejamos executar a partir do Tcl. Por exemplo,
um nó solicitar entrada, e um nó deixar anel - \textit{``soliciting''} e \textit{``stopping''}, respectivamente.

O método \textit{recv()} é invocado sempre que um agente de roteamento receber um pacote. A partir desse método
conferimos se o pacote é para encaminhar para camada de Agente, se é pacote de dados, ou se o pacote é de controle
(roteamento). Se for este último, o pacote é entregue a \textit{recv\_protocol\_packet(Packet* packet)} para
processar de acordo com tipo de pacote (\textit{SOLICIT\_ENTERING, NORMAL\_TOKEN,} etc).

A função \textit{send\_token\_packet(nsaddr\_t destination, u\_int8\_t frameControl,
		Packet *packet, int packet\_size, double delay)} agenda (para \textit{delay}) envio de pacote
de tamanho \textit{packet\_size}, do tipo \textit{frameControl} para o destinatário \textit{destination}.

\subsection{wtrp\_packet.h}
\label{impl:packeth}
O arquivo wtrp\_packet.h contém definições de estruturas de tabela de conectividade,
lista de nódos escutados, lista de identificadores em um anel. Também contém descrição de estados
em que um nódo pode se encontrar.
\subsection{node.h}
\label{impl:node}

\begin{lstlisting}[label=nodeheader, caption=node.h]
enum State {
	ON,
	RESET,
	OFFLINE,
	SOLICITING,
	JOINING,
	MONITORING,
	HAVING,
	IDLE_INRING,
	VARAL_OFFLINE,
	VARAL_SOLICITING,
	VARAL_JOINING,
	VARAL_MONITORING,
	VARAL_HAVING,
	VARAL_IDLE
};

/*Definition of a cell for connectivity tables*/
struct ConnectivityTableCell_ {
	... ... ...
};

struct Pair_ {
	... ... ...
};

struct Repliers_struct_ {
	... ... ...
};

struct FindByAddress {
	... ... ...
};

class Node_ {

      ... ... ...
};
#endif /* NODE_H_ */
\end{lstlisting}

O node.h (trecho \ref{nodeheader}) contém uma enumeração (\textit{State}) que define os possíveis estados de um nódo;
as estruturas que definem campos das tabelas e listas de um nódo; e a classe \textit{Node\_}
que define todos os atributos inerentes a um nódo dentro e fora de um anel. 

\subsection{ringutils.h e ringutils.cc}
\label{impl:ringutils}
Esses dois arquivos contêm funções que auxiliam o nódo no preparo de recepção
e transmissão de pacotes.

\subsection{utils-constants.h}
\label{impl:constants}
Contém definições das constantes usadas em temporizadores e em inicializações de
atributos de nódos.

\section{Arquivos alterados}

Nesta seção apresentaremos os arquivos que fazem parte da ferramenta NS2 e que
tivemos que alterar para ter o nosso protocolo funcionando.
\subsection{Arquivos em C++ e o \textit{Makefile}}
\label{impl:cplusplus}

\begin{itemize}
 \item Makefile
 \begin{lstlisting}[label=makefile, caption=Ligação de objetos do protocolo no Makefile]
	manet-trp/wtrp.o manet-trp/ringutils.o \
 \end{lstlisting}

 \item packet.h no diretório ns-2.35$\slash{common}$
 \begin{lstlisting}[label=tipopacote, caption=Definição de tipo de pacote]
 //WTRP packets
static const packet_t PT_WTRP = 75;

// insert new packet types here
static packet_t PT_NTYPE = 76; // This MUST be the LAST one
\end{lstlisting}
 No arquivo packet.h adicionamos um tipo de pacote (\ref{tipopacote}) que permite
NS2 reconhecer pacotes do nosso protocolo. Ademais, dentro da classe \textit{Packet},
adicionamos uma variável \textit{received\_power\_} (\ref{receivedpower}) para armazenar
energia recebida com um pacote.
\begin{lstlisting}[label=receivedpower, caption=Armazenamento de energia recebida]
 #ifdef WTRP_PREPROCESSOR
	double received_power_;
	inline double get_received_power() const {
		return received_power_;
	}
#endif
\end{lstlisting}
 \item priqueue.cc
 O tipo de fila implementado no arquivo trata pacotes de roteamento do protocolo WTRP 
 como de alta prioridade. Para tal precisamos avisar a classe \textit{Priqueue} que
 pacotes de WTRP são pacotes de roteamento.
 
 
 \item cmu-trace.h e cmu-trace.cc
 Nos arquivos cmu-trace e cmu-trace.cc criamos uma função para impressão de
 conteúdo entre camadas de um nó, e também para impressão
 de conteúdo trocados entre nódos.
 
 \item wireless-phy.cc no diretório $\slash{mac}$
 \begin{lstlisting}[caption=Atribuição de energia recebida com um pacote]
#ifdef WTRP_PREPROCESSOR
		p->received_power_ = Pr;
#endif
 \end{lstlisting}
 Para fazer energia recebida chegar a agente WTRP, além das alterações (declarações)
 feita no arquivo packet.h tivemos que atribuir valor calculado (\textit{Pr}
 para pacote $p$) 
 
 através do método \textit{sendUp()} da classe \textit{WirelessPhy}
 \begin{lstlisting}[caption=Protótipo do método sendUp]
 int WirelessPhy::sendUp(Packet *p) {
	... ... ...
 }
 \end{lstlisting}
 do arquivo wireless-phy.cc
 
\end{itemize}

\subsection{Arquivos em OTcl}
\label{impl:otcl}

\begin{itemize}
 \item agent.tcl no diretório $\slash{tcl}\slash{lib}\slash$
 \begin{lstlisting}[label=agentsettingports, caption=Atribuição de portas em arquivo tcl]
 #WTRP patch
 Agent/WTRP instproc init args {
 	$self next $args
 }
 Agent/WTRP set sport_   0
 Agent/WTRP set dport_   0
 \end{lstlisting}
O trecho acima ilustra a atribuição de portas a agente de roteamento, onde
\textit{sport} é a porta de origem e \textit{dport} é a porta destino.

\item ns-default.tcl no diretório $\slash{tcl}\slash{lib}\slash$
 \begin{lstlisting}[label=binded_var, caption=Atribuição de valor padrão a variável em arquivo tcl]
#WTRP
Agent/WTRP set sort_repliers_by_ 0
 \end{lstlisting}

 Neste arquivo atribuimos valores padrão a variáveis que podem ser inicializadas (com valores mais adequados) em
 \textit{script} tcl e usadas em arquivos c++.
 
 \item ns-lib.tcl no diretório $\slash{tcl}\slash{lib}\slash$
  \begin{lstlisting}[label=node_creation, caption=Procedimento para criar um nódo em arquivo tcl]
 Simulator instproc create-wireless-node args {
	      ... ... ...
	      switch -exact $routingAgent_ {
		    WTRP {
		    	set ragent [$self create-wtrp-agent $node]
		    }
	      }
	      ... ... ...
 }	      
 \end{lstlisting}
 O trecho apresentado em \ref{node_creation} permite que um nó criado seja
 atachado a um agente de roteamento para o protocolo WTRP.
 
 \begin{lstlisting}[label=agent_creation, caption=Cria um agente WTRP]
  Simulator instproc create-wtrp-agent { node } {
	#  Create WTRP routing agent
	set ragent [new Agent/WTRP [$node node-addr]]
	$self at 0.0 "$ragent start"
	$node set ragent_ $ragent
	return $ragent
}
 \end{lstlisting}

 Em \ref{agent_creation} criamos um agente \textit{WTRP} com endereço \textit{node-addr} de um nódo. Esse
 agente é agendado para começar no instante 0.0 de simulação, e é atribuido como
 agente de roteamento para um nódo ~\cite{protoname}.
 
 
 \item ns-packet.tcl no diretório $\slash{tcl}\slash{lib}\slash$
 
\begin{lstlisting}[label=protocol_name, caption=Definição de nome do protocolo em arquivo tcl]
  set protolist {
	... ... ...
	#WTRP
	WTRP
}
\end{lstlisting}
Na definição da lista \textit{protolist} definimos um nome \textit{``WTRP''}
para o protocolo.
\end{itemize}

\section{Simulador de rede}
\label{sec:simulador}

%O que é?
O simulador de rede (NS versão 2)~\cite{ns2}, mais conhecido por ns2, é uma ferramenta de simulação que se baseia em evento discreto.

%Como é ?
Simulador NS é composto principalmente por duas linguagens de programação: C++ e OTcl (TCL orientado a objeto) \cite{teerawat_book}. Nas
linhas que se seguem apresentaremos arquitetura básica e estrutura de diretórios do NS.

\subsection{Revisão do conceito}
De um lado, simulações detalhadas de protocolos requerem que uma linguagem de programação possa eficientemente manipular \textit{bytes},
cabeçalhos de pacotes, e implementar algoritmos que funcionam sobre um grande conjunto de dados. Essas tarefas requerem eficiência em
tempo de execução. Por outro lado, uma grande parte de pesquisa em redes envolve configurações, diferentes alterações de parâmetros e
cenários, sem a necessidade de re-compilar a implementação de um protocolo. Para essas situações é importante a eficiência em tempo
de alteração de parâmetros e cenários. Para solucionar esses problemas NS usa duas linguagens de programação, a saber:
\begin{itemize}
 \item C++ é eficiente quanto ao tempo de execução e nem tanto quanto as alterações para recompilação.
 \item OTcl é ineficiente quanto a execução, mas eficiente quanto as alterações de cenários para simulação.
\end{itemize}

Depois de simulações, NS2 gera resultado de simulação (em texto) e (animação). Para interpretar esses resultados graficamente e interativamente,
ferramentas como NAM (animador de rede) e \textit{Xgraph} são usadas. Para analisar um comportamento de rede em particular, usuários podem extrair
um subconjunto relevante de dados de texto e transformá-lo em uma apresentação mais concisa.  
\subsection{Estrutura do diretório NS}
\begin{figure}[!hbtp]
\centering
\includegraphics[scale=0.3]{ns2_directory_structure.pdf}
\caption{Estrutura principal do NS}
\label{fig:estr_dir}
\end{figure}

Na figura~\ref{fig:estr_dir} apresentamos a estrutura principal do diretório do NS (versão 2-35) após a instalação. No diretório 
\textbf{ns-2.35} encontram-se todos os módulos necessários para executar simulações, no \textbf{tcltc-1.20} estão as classes que permitem
objetos e variáveis aparecerem em ambas as linguagens (C++ e OTcl); no diretório \textbf{\textit{common}} colocam-se os arquivos que permitem encaminhamento de pacotes
criados para um novo protocolo ou para um protocolo já existente.
  
Após instalação do NS, usuário tem a sua disposição alguns protocolos de roteamento pré-instalados (por exemplo, AODV~\cite{rehmani}). O usuário pode alterar
esses protocolos ou adicionar um novo. O Protoname~\cite{protoname} é uma boa referência para aprender como adicionar um novo protocolo.


\chapter{Os problemas de terminal oculto e terminal exposto}
\label{ape:hiddenexpost}

Neste capítulo introduzimos dois dos notáveis problemas em redes de natureza sem fio.

\begin{figure}[!hbtp]
\centering
\includegraphics[scale=0.4]{hidden-node-img.pdf}
\caption{O problema de terminal oculto}
\label{fig:hiddennode}
\end{figure}

O protocolo MAC CSMA (\textit{Carrier Sense Multiple Access} - vide Kleinrock, Tobagi 1975) que é utilizado em tecnologias 802.11, é simples e
intuitivo ~\cite{toumpis}. Porém, este protocolo sofre do problema de terminal (nó) oculto e do problema de terminal exposto.

Para explicar o problema de terminal oculto, consideremos a figura ~\ref{fig:hiddennode}. Os terminais 1 e 3 não escutam as transmissões entre si.
Se ambos utilizam CSMA e transmitirem sinais para o terminal 2 simultaneamente, poderá ocorrem colisão de sinais, e estes se auto-destruírem.

\begin{figure}[!hbtp]
\centering
\includegraphics[scale=0.4]{exposed-node-img.pdf}
\caption{O problema de terminal exposto}
\label{fig:exposednode}
\end{figure}

No problema de terminal exposto um terminal não transmite sinais se ele perceber que algum terminal na sua
vizinhança está transmitindo. Para explicar melhor o problema de terminal exposto, vamos considerar a figura \ref{fig:exposednode}. Consideremos que
o terminal 3 está usando o CSMA como protocolo MAC, e o terminal 2 está transmitindo pacotes para o terminal 1. Como terminal 2 escuta as 
transmissões do terminal 3 e vice-versa. Se o terminal 3 tiver pacotes para o terminal 4, então enquanto o terminal 2 transmite para o terminal 1, 
o terminal 3 não transmitirá pacotes para o nó 4. Consequentemente, o terminal 3 vai provocar disperdício de largura de banda.

%FALAR DE SOLUÇÕES PARA ESSES DOIS PROBLEMAS
\chapter{Implementação de energia recebida com um pacote no NS}
\label{ape:implrecvpower}
Quando um nó recebe um determinado pacote, ele recebe também a energia $Pr$ com a qual esse pacote
foi transmitido. Como desejávamos uma opção que permitisse organizar os pacotes de resposta, a cada solicitação de entra,
por energia de recebimento, então aproveitamos para implementar essa característica no nosso protocolo de seguinte modo:
quando um nó $X$ solicita entrada em um anel $R$, ele ordena (de forma decrescente em uma lista) os pacotes recebidos
em resposta a solicitação de entrada segundo $Pr$. Para que seja possível obter o $Pr$ na camada de roteamento
adicionamos as seguintes alterações:
\begin{itemize}
 \item Adicionamos um campo extra 
 \begin{lstlisting} 
 received_power_ 
 \end{lstlisting}
 no arquivo packet.h conforme explicado em \ref{receivedpower}.
 
 \item Atribuimos o valor $Pr$ ao 
 \begin{lstlisting} 
 received_power_ 
 \end{lstlisting} 
 no arquivo wireless-phy.cc ao adicionar a instrução
 \begin{lstlisting} 
#ifdef WTRP_PREPROCESSOR
		p->received_power_ = Pr;
#endif
 \end{lstlisting}  
 no método 
 \begin{lstlisting}
 int WirelessPhy::sendUp(Packet *p) {
	... ... ...
 }
 \end{lstlisting}
 \item No arquivo wtrp.cc conseguimos ler o valor de $Pr$ uma vez que 
 \begin{lstlisting} 
 received_power_ 
 \end{lstlisting}
 está armazenada no pacote recebido. 
\end{itemize}
 Assim foi possível ter (no arquivo wtrp.cc) o valor de $Pr$ associado a um pacote sem quebrar
 a arquitetura do NS2.